package com.lw.algorithm.base;

import com.lw.algorithm.service.CalTimeService;
import com.lw.algorithm.utils.CalTimeUtils;
import com.lw.algorithm.utils.TestCaseUtils;

/**
 * 快速排序
 * @author Administrator
 *
 */
public class QuickSort implements CalTimeService{
	
	private int partition(int []array,int lo,int hi){
        //固定的切分方式
        int key=array[lo];
        while(lo<hi){
            while(array[hi]>=key&&hi>lo){//从后半部分向前扫描
                hi--;
            }
            array[lo]=array[hi];
            while(array[lo]<=key&&hi>lo){//从前半部分向后扫描
                lo++;
            }
            array[hi]=array[lo];
        }
        array[hi]=key;
        return hi;
	}
	
	private void sort(int[] array,int lo ,int hi){
		if(lo>=hi){
            return ;
        }
        int index=partition(array,lo,hi);
        sort(array,lo,index-1);
        sort(array,index+1,hi); 
	}

	public void excute(int[] arr) {
		sort(arr,0,arr.length - 1);
	}
	
	public static void main(String[] args) {
		int[] arr = TestCaseUtils.getRandomArray(1000000, 10000);
		CalTimeService calTime = new QuickSort();
		CalTimeUtils.excute(calTime, arr);
	}
}
